/**
 * 给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
 *
 *https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
 */
class MinimumDeleteSum {
    /**
     * 正常的动规
     * @param s1
     * @param s2
     * @return
     */
    public int minimumDeleteSumDpTable(String s1, String s2) {
         int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.codePointAt(i - 1);
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + s2.codePointAt(j - 1);
        }
        for (int i = 1; i <= m; i++) {
            int code1 = s1.codePointAt(i - 1);
            for (int j = 1; j <= n; j++) {
                int code2 = s2.codePointAt(j - 1);
                if (code1 == code2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + code1, dp[i][j - 1] + code2);
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 递归版动规
     */
    int[][] memo;
    public int minimumDeleteSumDpMemo(String s1, String s2) {
         int n=s1.length();
         int m=s2.length();
         memo=new int[n][m];
         for(int[] row:memo) {
             Arrays.fill(row,-1);
         }
        return dpMemo(s1,0,s2,0);
    }
    public int dpMemo(String s1,int i,String s2,int j) {
        int res=0;
        if(i==s1.length()) {
            for(int k=j;k<s2.length();k++) {
                res+=(int)s2.charAt(k);
            }
            return res;
        }
        if(j==s2.length()) {
            for(int k=i;k<s1.length();k++) {
                res+=(int)s1.charAt(k);
            }
            return res;
        }
        if(memo[i][j]!=-1) {
            return memo[i][j];
        }
        if(s1.charAt(i)==s2.charAt(j)) {
            memo[i][j]=dpMemo(s1,i+1,s2,j+1);
        } else {
            memo[i][j]=Math.min(
                s1.charAt(i)+dpMemo(s1,i+1,s2,j),
                s2.charAt(j)+dpMemo(s1,i,s2,j+1)
            );
        }
        return memo[i][j];
    }
}